At some point in my calculus education I developed a simple rule, when in doubt set the derivative equal to zero and solve for x. You might recall doing this, and the reason for doing it is because for a smooth function its local maximum and minimum are found at places where the derivate is zero. Imagine if you have curve shaped like a hill, now if you go up the hill and at some point go over the top (the max), if you keep going you will start traveling downward. If you went from increasing to decreasing, the calculus argument was that at some point your rate of increase was zero and that would be at the top. Largely this works very well. It leads nicely to many optimization rules, but it breaks down a little bit when we don't have a curve. In particular it breaks down when our domain is the set of integers.
Often times the problems are stated as find the "best" route, or find the "best" fitting function. For us to solve these problems, we need to model what "best" means. We need to mathematically describe a quantity to either maximize or minimize. For example we might seek select the route that minimizes the total distance traveled by a salesman (traveling salesman). Or if we were trying to fit a curve to some data, we might minimize the error between the predicted curve and the data (regression). We might try to select paths in a distribution network that maximize flow (network flow problems) etc.
When we talk about programs, we mean a set of variables, a function of those variables to maximize or minimize, and some constraints that those variables must satisfy.
formally:
We will see that the form of this optimization metric $f(x)$ plays a huge role in the difficulty. The first best case is when $f(x)$ and the constraints $g(x)$ are linear.
A linear program is one where the metric or objective to minimize is linear and the constraints are linear, i.e.:
If all the variables are continuous life is good. If however the variables must take on integer solutions, for example, 1,2,3... then life can be very hectic. Problems with integer only solutions are integer programming problems and they can be very difficult to solve if a solution exists at all! When you have a mix of variable types, you have a mixed integer problem. While many algorithms exist to solve all of these types, the most common for continuous programs is the simplex algorithm and for mixed integer the insanely clever branch cut and bound method works very well. We will talk about these later.
How do you know if the program is linear? just make sure the expression and the constraints are a combination of constants multiplied by some variables. If any of variables are multiplied or divided by another, you are in trouble and you have a harder problem. It is also important that the variables be continuous. If for example Most interesting problems are not linear, however there are a number approximations and tricks that can turn non linear programs into linear ones. We will explore this later. For now, lets solve our first program using PuLP.
In [3]:
#load all the things!
from pulp import *
lets try a small problem we can easily solve by hand
$$minimize\: f(x,y,z)=5x+10y+6z \\ subject\, to\\ x+y+z \geq 20 \\ 0\leq x,y,z \leq 10 $$In school we may have learned how to solve these types or problems by writing them in canonical form and throwing some linear algebra at them. PuLP is a library that removes this need, we can code our problem almost exactly as stated above in PuLP and it will do the hard work for us. What PuLP actually does is format the problem into a standard language that is used by many numerical solvers.
In [4]:
prob = LpProblem("Hello-Mathematical-Programming-World!",LpMinimize)
In [5]:
x = LpVariable('x',lowBound=0, upBound=10, cat='Continuous')
y = LpVariable('y',lowBound=0, upBound=10, cat='Continuous')
z = LpVariable('z',lowBound=0, upBound=10, cat='Continuous')
In [6]:
objective = 5*x+10*y+6*z
what does this create?
In [7]:
print(type(objective))
It is an LpAffineExpression. You can actually print LpAffineExpressions to see what you have programmed. Be careful with this on larger problems
In [8]:
print(objective)
In [9]:
constraint = x + y + z >= 20
In [10]:
#add the objective
prob+= objective
#add the constraints
prob+=constraint
like the LpAffineExpression class, we can print the problem to see what PuLP has generated. This is very useful for small problems, but can print thousands of lines for large problems. Its always a good idea to start small.
In [11]:
print(prob)
In [12]:
%time prob.solve()
print(LpStatus[prob.status])
In [13]:
#get a single variables value
print(x.varValue)
In [14]:
#or get all the variables
for v in prob.variables():
print(v, v.varValue)
In this example, the optimal objective is {{x.varValue}}
and the variables that give us that answer are: {{[q.varValue for q in prob.variables()]}}
In [ ]: